|
週次 |
日期 |
單元主題 |
|
Week 1 |
9/13 |
Course Overview, Algorithms and Complexity and Basics of Optimization |
|
Week 2 |
9/20 |
Linear Programming: Problems, Properties and Simplex Algorithms |
|
Week 3 |
9/27 |
Basic Properties of Linear Programming:
Linear programming example,
Basic feasible solutions,
Geometry of LP;
The R evised Simplex Algorithm:
Basics,
The algorithm
|
|
Week 4 |
10/04 |
Introduction to Mixed Integer Linear Programming;
Introduction to ILOG CPLEX Engine;
Applications of ILOG OPL and CPLEX
|
|
Week 5 |
10/11 |
The Revised Simplex Algorithm (Cont.):
algorithm;
Getting an Initial Feasible Solution;
Duality; |
|
Week 6 |
10/18 |
Duality:
Duality Theorem for Linear programming;
Complementary Slackness;
Sensitivity and Interpretation;
2. Network Optimization Problem:
Network representation and basics;
Some graph related definitions;
3. Minimum Spanning Tree Problems:
Problem description and greedy algorithm;
Mathematical Formulation;
Optimality proof;
4. Maximum Flow Problem:
Minimum cut, max flow and duality;
Ford-Fulkerson algorithm;
|
|
Week 7 |
10/25 |
1. Total Unimodularity;
2. Minimum cut, max flow and duality;
3. Ford-Fulkerson algorithm
4. Minimum Cost Network Flow Problems:
|
|
Week 8 |
11/01 |
1. Minimum Cost Network Flow Problems: 2. Bipartite matching 3. Transformation among network problems |
|
Week 9 |
11/08 |
Bipartite matching
Weighted matching
Application example: Weapon target assignment problem
Integer Linear Programming
Branch & Bound
A*-Search
Cutting Plane method (Gomory’s Cut)
|
|
Week 10 |
11/15 |
1. A*-Search Optimality (Cont.)
2. Cutting Plane method (Gomory’s Cut)
3. Traveling Salesman Problems
|
|
Week 11 |
11/22 |
mid-term exam |
|
Week 12 |
11/29 |
General Scheduling Problem Formulation;
Single Machine Scheduling;
Parallel Machine Scheduling;
Flow Shop Scheduling and Rescheduling.
|
|
Week 13 |
12/06 |
Parallel Machine Scheduling;
Flow Shop Scheduling and Rescheduling;
Term Project Idea Presentation
|
|
Week 14 |
12/13 |
Term Project Idea Presentation (Part II);
Flow Shop Scheduling and Rescheduling;
Local Search;
Meta-Heuristic Search;
Specific Search Strategies;
|
|
Week 15 |
12/20 |
Flow Shop Scheduling and Rescheduling:
1. Minimum cost network flow for solving; subproblems of individual products;
2. Duality gap and feasibility adjustment;
Local Search;
Meta-Heuristic Search;
Specific Search Strategies;
Simulated Annealing;
Stochastic Machines;
Convergence Analysis; |
|
Week 16 |
12/27 |
•Ordinal Optimization for deterministic problems
•Introduction to stochastic simulation
•Stochastic simulation optimization
•Some useful approaches
–Ordinal Optimization (OO)
–Optimal Computing Budget Allocation (OCBA) |
|
Week 17 |
1/03 |
Introduction to constraint programming |
|
Week 18 |
12/01/17 |
Term project presentation |
|
Week 2-1 |
09/20 |
補充教材 |